package Queue;

import java.util.*;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-05
 * Time:19:43
 * Text：103. 二叉树的锯齿形层序遍历
 */
public class Text2 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if(root==null) return list;
        Queue<TreeNode> t1=new ArrayDeque<>();
        int bz=1;
        t1.add(root);
        while(!t1.isEmpty()){
            int size=t1.size();
            List<Integer> t3=new ArrayList<>();
            Stack<TreeNode> t4=new Stack<>();
            //此时为顺序
            if(bz==0){
                Queue<TreeNode> t2=new ArrayDeque<>();
                //把存储在t1的结点全部遍历出来，存放在t2中
                for(TreeNode node: t1){
                    t3.add(node.val);
                    if(node.right!=null){
                        t4.push(node.right);
                    }
                    if(node.left!=null){
                        t4.push(node.left);
                    }
                }
                while(!t4.empty()){
                    t2.add(t4.pop());
                }
                t1=t2;
                bz=1;
                list.add(t3);
            }else{
                Queue<TreeNode> t2=new ArrayDeque<>();
                for(TreeNode node: t1){
                    t3.add(node.val);
                    if(node.left!=null){
                        t4.push(node.left);
                    }
                    if(node.right!=null){
                        t4.push(node.right);
                    }
                }
                while(!t4.empty()){
                    t2.add(t4.pop());
                }
                t1=t2;
                bz=0;
                list.add(t3);
            }
        }
        return list;
    }
}
